//
// Created by Administrator on 2025/8/7.
//

#ifndef DOUBLELIST_H
#define DOUBLELIST_H
#include <memory>

namespace double_list {
    struct node {
        explicit node(const int val = 0) : data_(val), next_(nullptr), prev_(nullptr) {}
        int data_;
        node *next_;
        node *prev_;
    };
    class iterator {
    public:
        explicit iterator(const node* ptr=nullptr) : ptr_(ptr) {}
        void operator++(int) {
            ptr_ = ptr_->prev_;
        }
        void operator--(int) {
            ptr_ = ptr_->next_;
        }
        bool operator!=(const iterator& it) const {
            return ptr_ !=it.ptr_;
        }
        int operator*() const {
            if (ptr_!=nullptr) {
                return ptr_->data_;
            }
            return -1;
        }
    private:
        const node *ptr_;
    };

class doubleList {
public:
    explicit doubleList() {
        head_ = new node();
        tail = head_;
    }
    ~doubleList() {
        // 如果头节点为空，则直接返回
        if (head_==nullptr) {
            return ;
        }
        if (head_->next_==nullptr) {
            delete head_;
            head_ = nullptr;
            return;
        }
        // 定义一个指针p，指向头节点的下一个节点
        node* p = head_->next_;
        // 当p不等于头节点时，循环执行以下操作
        while (p!=nullptr) {
            // 定义一个指针prev，指向p的前一个节点
            node *prev = p->prev_;
            // 定义一个指针next，指向p的后一个节点
            node* next = p->next_;
            // 将p的前一个节点的next指针指向p的后一个节点
            prev->next_ = next;
            // 将p的后一个节点的前一个指针指向p的前一个节点
            if (next!=nullptr) {
                next->prev_ = prev;
            }else {
                tail = prev;
            }
            // 删除p节点
            delete p;
            // 将p指针指向p的后一个节点
            p = prev->next_;
        }
        delete head_;
        head_ = nullptr;
    }
    //在尾部插入一个节点
    void insertNode(const int val) {
        // 创建一个新节点，值为val
        const auto  newNode = new node(val);
        // 如果新节点不为空
        if (newNode!=nullptr) {
            // 将新节点的next_指向tail
            tail->next_ = newNode;
            // 将新节点的prev_指向tail
            newNode->prev_ = tail;
            // 将tail指向新节点
            tail = newNode;
        }
    }
    //在头部插入一个节点
    void insertNodeHead(const int val) {
        // 创建一个新节点
         auto newNode = new node(val);
        // 如果新节点不为空
        if (newNode!=nullptr) {
            // 保存当前头节点的下一个节点
            node* next = head_->next_;
            // 将头节点的下一个节点指向新节点
            head_->next_ = newNode;
            newNode->next_ = next;
            newNode->prev_ = head_;
            if (next==nullptr) {
                tail = newNode;
            }else {
                next->prev_ = newNode;
            }
        }
    }
    //删除尾部节点
    void deleteNode() {
        // 获取尾节点的上一个节点
        node *prev = tail->prev_;
        // 如果上一个节点不为空且尾节点不等于头节点
        if (prev!=nullptr&& tail !=head_) {
            // 将上一个节点的下一个节点置为空
            prev->next_ = nullptr;
            // 将尾节点的上一个节点置为空
            tail->prev_ = nullptr;
            // 删除尾节点
            delete tail;
            // 将尾节点指向上一个节点
            tail =prev;
        }
    }
    //删除尾部节点
    void headDeleteNode() {
        // 获取头节点的下一个节点
        const node* next = head_->next_;
        // 如果下一个节点不为空
        if (next!=nullptr) {
            // 将头节点的下一个节点指向下一个节点的下一个节点
            head_->next_ = next->next_;
            // 将下一个节点的下一个节点的上一个节点指向头节点
            next->next_->prev_ = head_;
            // 删除下一个节点
            delete next;
            // 将下一个节点置为空
            next = nullptr;
            // 如果头节点的下一个节点为空，将尾节点指向头节点
            if (head_->next_ == nullptr) {
                tail = head_;
            }
        }
    }
    //删除指定的元素
    void deleteNodeByValue(const int val) {
        // 如果链表为空，直接返回
        if (isEmpty()) {
            return;
        }
        const node* cur = head_->next_;
        while (cur!=nullptr) {
            if (cur->data_ == val) {
                //找到前一个节点
                node* pre = cur->prev_;
                //找到后一个节点
                node* next = cur->next_;
                //将前一个节点的next指向后一个节点
                pre->next_ = next;
                //将后一个节点的prev指向前一个节点
                if (cur != tail) {
                    next->prev_ = pre;
                }else {
                    tail = pre;
                }
                delete cur;
                cur = nullptr;
                break;
            }
            cur = cur->next_;
        }

    }
    //删除指定的元素，删除多个
    void deleteAllNodeByValue(const int val) {
        // 判断链表是否为空，如果为空则直接返回
        if (isEmpty()) {
            return;
        }
        const node* cur = head_->next_;
        while (cur!=nullptr) {
            if (cur->data_ == val) {
                //找到前一个节点
                node* pre = cur->prev_;
                //找到后一个节点
                node* next = cur->next_;
                //将前一个节点的next指向后一个节点
                pre->next_ = next;
                //将后一个节点的prev指向前一个节点
                if (cur != tail) {
                    next->prev_ = pre;
                }else {
                    tail = pre;
                }
                delete cur;
                cur = pre->next_;
            }else {
                cur = cur ->next_;
            }
        }
    }
    //查看是不是存在这个元素
    // 判断链表中是否存在值为val的元素
    bool isExist(const int val) const{
        // 如果链表为空，则返回false
        if (head_==nullptr) {
            return false;
        }
        // 遍历链表，判断是否存在值为val的元素
        for (node* p = head_->next_;p!=nullptr;p=p->next_) {
            // 如果找到值为val的元素，则返回true
            if (p->data_ == val) {
                return true;
            }
        }
        // 如果遍历完链表仍未找到值为val的元素，则返回false
        return false;
    }
    //这个链表是不是空
    bool isEmpty() const { return head_==nullptr || head_ == tail; }
    //打印链表
    void printList()const {
        // 判断链表是否为空，如果为空则直接返回
        if (isEmpty()) {
            return;
        }
        // 遍历链表，输出每个节点的数据
        for (node* p= head_->next_;p!=nullptr;p=p->next_) {
               std::cout<<p->data_<<" ";
        }
        // 输出换行符
        std::cout<<std::endl;

    }
    //迭代器的形式反向显示链表
    iterator sbegin() const{
        return iterator(tail);
    }
    //迭代器的形式反向显示链表
    iterator send() const {
        return iterator(head_);
    }



private:
    node* head_;
    node* tail;
};

} // double_list

#endif //DOUBLELIST_H
